/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class ClimbingStairs {

	/**
	You are climbing a stair case. It takes n steps to reach to the top.

	Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
	
	dp
	完成第n步独立方法的是由完成前一步和前两步的独立方法之和
	step[n] = step[n - 1] + step[n - 2]
	 */
	public int climbStairs(int n) {
		assert (n > 0);
		if (n <= 2)
			return n;
		int step1 = 1, step2 = 2, curr = 0;
		for (int i = 3; i <= n; i++) {
			curr = step1 + step2;
			step1 = step2;
			step2 = curr;
		}

		return curr;
	}

	/**
	 * 
	 */
	public ClimbingStairs() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
